|
|
Two-phase scheduling with unknown speeds
Minařík, Josef ; Sgall, Jiří (vedoucí práce) ; Eberle, Franziska (oponent)
Rychlostně robustní rozvrhování je dvoufázový rozvrhovací problém. Na vstupu je dána doba běhu pro každý z n úkolů, počet strojů m a počet balíčků b. Naším úkolem je rozdělit úkoly do balíčků, které budou následně zpracovány na strojích, které mají v tomto okamžiku neznámé rychlosti. Naším cílem je minimalizovat poměr délky našeho rozvrhu a délky optimáního rozvrhu, který by vznil umisťováním úkolů rovnou na stroje. Nejpodrobněji studovaný případ doposud byl b = m. V této práci zobecňujeme známé výsledky pro infinitizemálně malé úkoly (tento případ se nazývá písek) a dokážeme, že nejlepší kompetitivní poměr, kterého je možné dosáhnout, je mb mb−(m−1)b . Dále formulujeme algoritmus řešící případ s identickými úkoly (nazývaný cihly) za podmínky b = m s kompetitivním poměrem 1.6, což zlepšuje nejlepší doposud známou hodnotu 1.8. Zavedeme nový speciální případ, který budeme nazývat p-oblázky. V tomto případě jsou doby běhu jednotlivých úkolů nejvýše p-násobky průměrné zátěže stroje. Oblázky jsou vlastnostmi i obtížností na půl cesty mezi pískem a obecným případem (nazývaným kameny). Popíšeme algoritmus pro oblázky, který je pro malé hodnoty p lepší než nejlepší známý algoritmus pro kameny (pro p menší než 2 − e e−1 v případě b = m). 1
|
host ::
RSS.